package buildTree102;


public class BuildTree {

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return build(preorder, 0, preorder.length - 1,inorder, 0, inorder.length - 1);
    }

    /**
     * @param preorder
     * @param preStart 前序开始索引下标
     * @param preEnd 前序结束索引下标
     * @param inorder
     * @param inStart
     * @param inEnd
     * @return
     */
    public TreeNode build(int[] preorder,int preStart,int preEnd, int[] inorder,int inStart,int inEnd){
        //基础条件判断
        if(preStart>preEnd){
            return null;
        }
        //先确定跟节点，根节点就是前序遍历的第一个元素
        int rootVal = preorder[preStart];
        TreeNode root = new TreeNode(rootVal);

        //在中序遍历数组中寻找根节点的位置索引，该位置左侧就是左子树，右侧就是右子树。
        int index = 0; //根节点在中序数组中位置
        for (int i = 0; i <inorder.length ; i++) {
            if(rootVal == inorder[i]){
                index = i;
                break;
            }
        }
        //可以确定左子树的元素个数
        int leftSize = index - inStart;
        //递归左子树
        root.left = build(preorder,preStart + 1,preStart+leftSize,inorder,inStart,index-1);
        //递归右子树
        root.right = build(preorder,preStart+ leftSize + 1,preEnd,inorder,index+1,inEnd);

        return root;
    }

}
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}